BZOJ 1532 Kos-Dicing

Description

Dicing 是一个两人玩的游戏,这个游戏在Byteotia非常流行. 甚至人们专门成立了这个游戏的一个俱乐部. 俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.

Input

第一行两个整数n 和 m, 1 <= n <= 10 000, 0 <= m <= 10 000; n 表示一共有多少个参赛者, m 表示有多少场比赛. 选手从1 到 n编号. 接下来m 行每行两个整数表示该场比赛的两个选手,两个选手可能比赛多场.

Output

第一行表示赢得最多的人最少会赢多少场

Sample Input

4 4

1 2

1 3

1 4

1 2

Sample Output

1

Solution

2014cyb集训队论文
二分图的dinic是n√m的
长见识了= =

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>

#define maxn 20000+5
#define maxm 80000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v,c;
int next;
}s[maxm];

queue<int> q;
int h[maxn];
int first[maxn],cur[maxn],ind,label;
int n,m,S,T,ans;

void insert(int u,int v,int w)
{

s[ind]=(sides){u,v,w,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,0,first[v]},first[v]=ind++;
}

void init(int flow)
{

for(int i=0;i<ind;i+=2)
s[i].c=s[i].c+s[i^1].c,s[i^1].c=0;
for(int i=label;i<ind;i+=2)
s[i].c=flow;
}

bool bfs()
{

set(h,-1),h[T]=0;
q.push(T);
while( !q.empty() ){
int sd=q.front();q.pop();
for(int i=first[sd];i!=-1;i=s[i].next)
if( s[i^1].c>0 && h[s[i].v]==-1 ){
h[s[i].v]=h[sd]+1;
q.push(s[i].v);
}
}
return h[S]!=-1;
}

int dfs(int x,int flow)
{

if( x==T ) return flow;
int used=0;
for(int &i=cur[x];i!=-1;i=s[i].next)
if( h[s[i].v]==h[x]-1 && s[i].c>0 ){
int w=dfs(s[i].v,min(flow,s[i].c));
s[i].c-=w,s[i^1].c+=w;
used+=w;
if( flow==used ) return flow;
}
return used;
}

bool dinic(int flow)
{

int res=0;
while( bfs() ){
for(int i=S;i<=T;i++)
cur[i]=first[i];
res+=dfs(S,INT_MAX);
}
return res==m;
}

void div2()
{

int l=0,r=m;
while( l!=r ){
int mid=(l+r)/2;
init(mid);
if( dinic(mid) ) r=mid;
else l=mid+1;
}
ans=l;
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1532.in","r",stdin);
freopen("1532.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
set(first,-1);
S=0,T=n+m+1;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
insert(S,i+n,1);
insert(i+n,u,1),insert(i+n,v,1);
}
label=ind;
for(int i=1;i<=n;i++) insert(i,T,0);
div2();
printf("%d",ans);
return 0;
}